package com.clstu.leetcode;

/**
 * leetcode  62题,不同路径,动态规划问题
 */
class Solution7 {

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        System.out.println(uniquePaths(51,9));
        long end = System.currentTimeMillis();
        System.out.println("耗时:"+(end-start)+"ms");
    }

    public  static int uniquePaths(int m, int n) {
        int[][] dp = new int[m+1][n+1];
        //全部初始化位-1,表示没有计算过
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                dp[i][j] = -1;
            }
        }
        return dfs2(1,1,m,n,dp);
    }

    //暴力递归到动态规划
    public static int dfs(int x,int y,int m,int n){
        //如果走到右下角,说明找到一种方法,返回
        if(x==m && y==n) return 1;
        //如果走到最右,只能向下走
        if(x == m){
            return dfs(x,y+1,m,n);
        }
        //如果到最下,只能向右走
        if(y==n){
            return dfs(x+1,y,m,n);
        }
        //否则,就既可以向下也可以向右
        return dfs(x+1,y,m,n) + dfs(x,y+1,m,n);
    }

    //暴力递归----动态规划,第二版,加入dp
    public static int dfs2(int x,int y,int m,int n,int[][] dp){
        //先查dp,如果已将算过直接返回即可
        if(dp[x][y] != -1){
            return dp[x][y];
        }
        //记录答案最后返回前存入到dp中,下次调用相同的过程直接就能从dp种拿数据,减少计算时间
        int ans = 0;
        if(x==m && y==n){
            ans = 1;
        }else if(x==m){
            ans = dfs(x,y+1,m,n);
        }else if(y==n){
            ans = dfs(x+1,y,m,n);
        }else{
            ans = dfs(x,y+1,m,n) + dfs(x+1,y,m,n);
        }
        //计入dp,再返回
        dp[x][y] = ans;
        return ans;
    }
}
